package top.wuchu.rpc.loadbalancer;

import com.alibaba.nacos.api.naming.pojo.Instance;

import java.util.*;

/** 本负载均衡算法跟传统负载均衡不一样
 *  传统负载均衡默认所有服务提供的服务接口一样，用户的请求分到哪个服务器都行
 *  一致性Hash算法认为每个服务器提供的服务不一样，每一个客户端的请求需要去
 * @author: WuChu
 * @create: 2023-08-05 15:56
 * @description:
 **/
public class IpHashLoadBalancer implements LoadBalancer {


    //TreeMap中的key表示服务器的hash值，value表示服务器ip。模拟一个哈希环
    private static TreeMap<Integer,String> Nodes = new TreeMap();

    private static int VIRTUAL_NODES = 160;//虚拟节点个数，用户指定，默认160,

    public static HashMap<String,Instance> map = new HashMap<>();//将服务实例与ip地址一一映射

    // 了解一致性Hash算法的原理，在本RPC系统中是一个真实的服务IP映射到160个虚拟节点



    /**
     *
     * @param instances
     * @return 经过一致性Hash算法计算之后最终得到的服务实例
     */
    @Override
    public Instance select(List<Instance> instances, String clientAddress) {

        //预处理 形成哈希环
        //程序初始化，将所有的服务器(真实节点与虚拟节点)放入Nodes（底层为红黑树）中
        for (Instance instance : instances) {
            String ip = instance.getIp(); // 服务端的IP地址

            // 存储真实节点
            Nodes.put(getHash(ip),ip);
            map.put(ip,instance);
            for(int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(ip+"#"+i);
                // 存储虚拟节点
                Nodes.put(hash,ip);
            }
        }
        return map.get(getServer(clientAddress));
    }



    /**
     * 在`TreeMap`的api中有一个`tailMap`() 函数，输入一个`fromKey`，输出的是一个`SortedMap`有序Map，
     * 再使用`firstKey`()拿到最近一个大于客户端哈希值的元素，也就是服务器的IP地址
     * @param clientInfo
     * @return 服务器IP
     */
    public  String getServer(String clientInfo) {
        int hash = getHash(clientInfo);

        //得到大于该Hash值的map
        SortedMap<Integer,String> subMap = Nodes.tailMap(hash);

        //获取该map最小元素
        Integer nodeIndex = subMap.firstKey();

        //没有大于该元素的子树 取整树的第一个元素(想象成一个环，超过尾部则取第一个 key)
        if (nodeIndex == null) {
            nodeIndex = Nodes.firstKey();
        }
        return Nodes.get(nodeIndex);
    }

    /**
     * 自定义Hash算法
     * @param str
     * @return
     */
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash^str.charAt(i))*p;
            hash +=hash <<13;
            hash ^=hash >>7;
            hash +=hash <<3;
            hash ^=hash >>17;
            hash +=hash <<5;
            //如果算出来的值为负数 取其绝对值
            if(hash < 0) {
                hash = Math.abs(hash);
            }
        }
        return hash;
    }

    @Override
    public Instance select(List<Instance> instances) {
        return null;
    }

}
